#include <stdio.h>
#include <stdlib.h>

int is_prime_1(int x)
{
    int i;

    for (i = 2; i*i <= x; i++) {
        if (x%i == 0)
            return 0;
    }

    return 1;
}

int montgmery(int a, int m, int x)
{
    int ret = 1;

    while (m) {
        if (m & 1)
            ret = (ret * a)%x;
        a *= a;
        m >>= 1;
    }

    return ret;
}

int is_prime_2(int x)
{
    if (x == 2)
        return 1;

    return montgmery(2, x-1, x) == 1;
}

int is_prime_3(int x)
{
    int i, j, a, r, m, e, n;
    
    if (x == 2)
        return 1;

    r = 0;
    m = x-1;
    while (!(m & 1)) {
        r ++;    
        m >>= 1;
    }

    for (i = 0; i < 50; i++) {
        a = rand()%(x-1) + 1;
        if ((n = montgmery(a, m, x)) == 1)
            continue;
        for (j = 0, e = 1; j < r; j++) {
            if ((n = montgmery(a, m*e, x)) == x-1)
                break;
            e <<= 1;
        }

        if (j == r)
            return 0;
    }

    return 1;
}

int main(int argc, char *argv[])
{
    int i;

    while (1) {
        scanf("%d", &i);

        if (i <= 1)
            break;

        printf("%d %s a prime number\n", i, 
            is_prime_1(i)?"is":"is not");
        printf("%d %s a prime number\n", i, 
            is_prime_2(i)?"is":"is not");
        printf("%d %s a prime number\n", i, 
            is_prime_3(i)?"is":"is not");
    }
    return 0;
}
